"""
1277. 统计全为 1 的正方形子矩阵
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。



示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：

输入：matrix =
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.


提示：

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
"""
from typing import List


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        """
        逻辑，对于2->3，只需要满足右下新增的节点的左，上，左上是2即可
        比如
        1 1 要变成三维则需要 1 1 1
        1 2               1 2 2
                          1 2 ?
        最后把数字相加即可，3为包括自身的所有正方形，从右下到左上，宽为1，2，3各一个
        :param matrix:
        :return:
        """
        n = len(matrix)
        m = len(matrix[0])
        status = True
        for x in range(2,301):
            #上次没有更新，后续也无意义
            if not status:
                break
            status = False
            for i in range(x-1,n):
                for j in range(x-1,m):
                    if matrix[i][j] == 0:
                        continue
                    #找到左，上，左上最小值，当最小值>= x-1 是，认为可以组成
                    minOne = min(matrix[i-1][j],matrix[i-1][j-1],matrix[i][j-1])
                    if minOne>=(x-1):
                        status = True
                        matrix[i][j] = x
        return sum(sum(x) for x in matrix)

if __name__ == '__main__':
    # dp = [[1,2],[3,4]]
    # print(sum(sum(x) for x in dp))
    matrix1 =[
        [0, 1, 1, 1],
        [1, 1, 1, 1],
        [0, 1, 1, 1]
    ]
    print(Solution().countSquares(matrix1))
